package com.arrayExamples;

import java.util.*;

/**
 * Created by yijy on 2017/8/11.
 *
 */
public class ArrayTest1 {
    public  static int[] arr={1,2,3,0,0,4,0,0,5};
    public static void main(String[] args) {
        ArrayTest1 test1 = new ArrayTest1();
        TreeNode  root = test1.createTreeNode();
        ArrayList<ArrayList<Integer>> lists = test1.levelOrder(root);
        for (ArrayList list:lists) {
            for(int i=0;i<list.size();i++){
                System.out.print(list.get(i)+"\t");
            }
            System.out.println();
        }
    }

    public TreeNode createTreeNode(){
        //构建二叉树
        TreeNode root1 = new TreeNode(arr[0]);
        TreeNode root2 = new TreeNode(arr[1]);
        TreeNode root3 = new TreeNode(arr[2]);
        TreeNode root4 = new TreeNode(arr[5]);
        TreeNode root5 = new TreeNode(arr[8]);
        root1.setLeft(root2);
        root1.setRight(root3);
        root3.setLeft(root4);
        root4.setLeft(root5);
        return root1;
    }

    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<TreeNode>();
        linkedList.offer(root);
        TreeNode current;
        ArrayList list1 = new ArrayList<ArrayList<Integer>>();
        List list = new ArrayList<Integer>();
        list.add(root.getVal());
        list1.add(list);
        while (!linkedList.isEmpty())
        {
            current = linkedList.poll();//将队头打印
            list = new ArrayList<Integer>();
            if(current.getLeft()!=null)
            {
                linkedList.offer(current.getLeft());
                list.add(current.getLeft().getVal());
            }
            if(current.getRight()!=null)
            {
                linkedList.offer(current.getRight());
                list.add(current.getRight().getVal());
            }
            if(list.size()>0){
                list1.add(list);
            }
        }
        return list1;
    }


    public class TreeNode{
        private TreeNode left;
        private TreeNode right;
        private int val;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }
}
